/*
	The MIT License

	Copyright (c) 2010 IFMO/GameDev Studio

	Permission is hereby granted, free of charge, to any person obtaining a copy
	of this software and associated documentation files (the "Software"), to deal
	in the Software without restriction, including without limitation the rights
	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	copies of the Software, and to permit persons to whom the Software is
	furnished to do so, subject to the following conditions:

	The above copyright notice and this permission notice shall be included in
	all copies or substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
	THE SOFTWARE.
*/

#include "ge_local.h"
#include <algorithm>

/*-----------------------------------------------------------------------------
	TriMesh experimental stuff :
-----------------------------------------------------------------------------*/

/*-----------------------------------------------------------------------------
	TriMesh splitting :
-----------------------------------------------------------------------------*/

const int LEFT   = 4;
const int RIGHT  = 2;
const int SPLIT  = 1;
const int RIGHT_SPLIT = RIGHT | SPLIT;
const int LEFT_SPLIT = LEFT | SPLIT;


void MakeTriangle(IPxTriMesh mesh, const EVertex* v0, const EVertex *v1, const EVertex *v2, EShadingGroup &sg){
	bool b1 = v0->position.IsEqual( v1->position, FLOAT_EPSILON );
	bool b2 = v1->position.IsEqual( v2->position, FLOAT_EPSILON );
	bool b3 = v2->position.IsEqual( v0->position, FLOAT_EPSILON );
	if ((b1 | b2 | b3))
		return;
	mesh->AddTriangle(*v0, *v1, *v2);
	sg.num++;
}


//
//	MakePolygon
//	Supports only CONVEX polygons
//
void MakePolygon(IPxTriMesh mesh, std::vector<EVertex*> verts, EShadingGroup &sg){
	if (verts.empty())
		return;
	EVertex* v0 = verts[0];
	for (uint i = 1; i < verts.size() - 1; i++){
		MakeTriangle(mesh, v0, verts[i], verts[i+1], sg);
	}
}


bool GetIntersection(EVertex& out, const EVertex *v0, const EVertex *v1, float k){
	out = *v0;
	if ( k > 0) return false;
	if (abs(k) < FLOAT_EPSILON) {
		return true;
	}
	float c = 1 - 1 / (abs(k) + 1);
	out.position	= v0->position.LerpTo	( v1->position, c );
	out.normal		= v0->normal.Lerp		( v1->normal,   c );
	out.uv0			= v0->uv0.LerpTo		( v1->uv0,		c );
	out.uv1			= v0->uv1.LerpTo		( v1->uv1,		c );
	out.binormal	= v0->normal.Lerp		( v1->binormal, c );
	out.tangent		= v0->normal.Lerp		( v1->tangent,  c );
	out.color0		= v0->color0.LerpTo		( v1->color0,	c );
	out.color1		= v0->color1.LerpTo		( v1->color1,	c );
	return true;
}


//
//	ETriMesh::Split
//	left and right meshes are not optimized
//
void ETriMesh::Split( const EPlane &plane, IPxTriMesh left, IPxTriMesh right )
{
	if (IsEmpty()) return;
	EVector normal(plane.a, plane.b, plane.c);
	normal.NormalizeSelf();

	left->SetFormat(GetFormat());
	right->SetFormat(GetFormat());

	EShadingGroup* curr_sg = &*shading_groups.begin();
	EShadingGroup left_sg;
	EShadingGroup right_sg;

	left_sg.shader = curr_sg->shader;
	right_sg.shader = curr_sg->shader;

	for (uint i = 0; i < triangles.size(); i++){
		
		if (curr_sg->num + curr_sg->start == i){
			left->AttachSG(left_sg);
			right->AttachSG(right_sg);
			curr_sg++;
			left_sg.shader = curr_sg->shader;
			right_sg.shader = curr_sg->shader;
			left_sg.start += left_sg.num;
			right_sg.start += right_sg.num;
			left_sg.num = 0;
			right_sg.num = 0;

		}

		EVertex *v[] = {&vertices[triangles[i].i0], 
						&vertices[triangles[i].i1],
						&vertices[triangles[i].i2]};
		float d[] = {	EMath::Dot( normal, EVector(v[0]->position) ) + plane.d,
						EMath::Dot( normal, EVector(v[1]->position) ) + plane.d,
						EMath::Dot( normal, EVector(v[2]->position) ) + plane.d	};
						
		const uint ver_num = _countof(v);
		int dn[ver_num];
		for (uint j = 0; j < ver_num; j++){
			dn[j] = 0;
			if (d[j] >= 0){
				dn[j] |= RIGHT;
			}
			if (d[j] <= FLOAT_EPSILON && d[j] >= -FLOAT_EPSILON){
				dn[j] |= SPLIT;
			}
			if (d[j] < 0){
				dn[j] |= LEFT;
			}
		}

		if ((dn[0] & RIGHT_SPLIT) && (dn[1] & RIGHT_SPLIT) && (dn[2] & RIGHT_SPLIT)){
			MakeTriangle(right, v[0], v[1], v[2], right_sg);
		}
		else if ((dn[0] & LEFT_SPLIT) && (dn[1] & LEFT_SPLIT) && (dn[2] & LEFT_SPLIT)){
			MakeTriangle(left, v[0], v[1], v[2], left_sg);
		}
		else {
			//continue;
			//	Polygon split by Sutherland-Hodgman algorithm
			std::vector<EVertex*> lvec, rvec;
			
			EVertex is[3];
			for (uint j = 0; j < ver_num; j++){
				uint to = j + 1;
				if (to == ver_num) to = 0;

				if (dn[j] & RIGHT){
					rvec.push_back(v[j]);
					if (dn[to] & LEFT){
						GetIntersection(is[j], v[j], v[to], d[j] / d[to]);
						rvec.push_back(&is[j]);
						lvec.push_back(&is[j]);
					}
				}
				else if (dn[j] & LEFT){
					lvec.push_back(v[j]);
					if (dn[to] & RIGHT){
						GetIntersection(is[j], v[j], v[to], d[j] / d[to]);
						rvec.push_back(&is[j]);
						lvec.push_back(&is[j]);
					}
				}
			}
			MakePolygon(left,  lvec, left_sg);
			MakePolygon(right, rvec, right_sg);
		}
	}
	left->AttachSG(left_sg);
	right->AttachSG(right_sg);
}


void ETriMesh::DeOptimize( void )
{
	std::vector<EVertex>	temp_vertices = vertices;
	uint sz = triangles.size();
	vertices.clear();
	//	Maybe make resize instead of reserve?
	vertices.reserve(sz * 3);
	for (uint i = 0, n = 0; i < sz; i++, n+=3){
		AddVertex(temp_vertices[triangles[i].i0]);
		AddVertex(temp_vertices[triangles[i].i1]);
		AddVertex(temp_vertices[triangles[i].i2]);
		triangles[i] = triangle_s(n, n+1, n+2);
	}
}


/*-----------------------------------------------------------------------------
	Ray/TriMesh intersection :
-----------------------------------------------------------------------------*/

//
//	ETriMesh::RayIntersect
//
bool ETriMesh::RayIntersect( const EPoint &origin, const EVector &direction, ITriMeshHitCB *report ) const
{
	struct hit_s {
		EVertex p;
		float	t;
		bool	into;
	};
	
	class SortByFrac {
	public:
		bool operator()	( const hit_s hit0, const hit_s hit1 ) {
			return (hit0.t < hit1.t);
		}
	} sort_by_frac;
	

	float	fraction;
	EPoint	point;
	bool	into;
	
	bool any_hit = false;
	std::vector<hit_s> hits;

	for (uint i = 0; i < triangles.size(); ++i) {
		const EPoint &A = vertices[triangles[i].i0].position;
		const EPoint &B = vertices[triangles[i].i1].position;
		const EPoint &C = vertices[triangles[i].i2].position;
		
		EVector n		=	TriangleNormal( i );
		float n_dot_r	=	EMath::Dot( n, direction );
		into = ( n_dot_r < 0 );
		
		bool r = Math_RayTriangleIntersection( point, fraction, origin, direction, A, B, C );
		any_hit |= r;

		if (r) {		
			hit_s hit;
			hit.p.position	=	point;
			hit.t			=	fraction;
			hit.into		=	into;
			
			hits.push_back( hit );
		}
	}
	
	sort( hits.begin(), hits.end(), sort_by_frac );
	
	float old_t = MIN_FLOAT_VALUE;
	for (uint i=0; i < hits.size(); i++) {
		if ( abs(old_t - hits[i].t) < 0.0001f) {
			continue;
		}
		old_t = hits[i].t;
		report->Callback( hits[i].p, hits[i].t, hits[i].into );
	}
	
	return any_hit;
}


//
//	ETriMesh::RayIntersect
//
bool ETriMesh::RayIntersect( const EPoint &origin, const EVector &direction, EVertex &result)   const
{
	bool  ret = false;	
	float fraction;
	EPoint point;
	
	float min_fraction  = MAX_FLOAT_VALUE;
	EPoint closest_point	= origin;

	for (uint i = 0; i < triangles.size(); ++i){
		const EPoint &A = vertices[triangles[i].i0].position;
		const EPoint &B = vertices[triangles[i].i1].position;
		const EPoint &C = vertices[triangles[i].i2].position;
		
		bool r = Math_RayTriangleIntersection( point, fraction, origin, direction, A, B, C );
		
		if (!r) {
			continue;
		}
		
		ret = true;
		
		if (fraction < min_fraction) {
			min_fraction	= fraction;
			closest_point	= point;
			result.position	= closest_point;
		}
	}
	
	return ret;
}


//
//	ETriMesh::Clear
//
void ETriMesh::Clear( void )
{
	triangles.clear();
	vertices.clear();
	shading_groups.clear();
}



/*-----------------------------------------------------------------------------
	Decals :
-----------------------------------------------------------------------------*/

//
//	TrimMesh
//
IPxTriMesh TrimMesh(const EPoint &v0, const EPoint &v1, const EPoint &v2, IPxTriMesh mesh)
{
	EPlane plane = PlaneFromPoints(v0, v1, v2);

	IPxTriMesh m1 = Geometry()->CreateTriMesh(mesh->GetFormat());
	IPxTriMesh m2 = Geometry()->CreateTriMesh(mesh->GetFormat());

	mesh->Split(plane, m1, m2);
	return m1;
}


bool ETriMesh::GetDecal( const EPoint &origin, const EVector &direction, float size, IPxTriMesh result, EVertex &v)
{
	NOT_IMPLEMENTED;
#if 0
	if (false == RayIntersect(origin, direction, v))
		return false;

	//	Calculating basis for box
	EVec3 normal = Vec3Normalize(v.normal);
	EVec3 side = Vec3Cross(normal, EVec3(0,1,0));
	side = Vec3Normalize(side);
	EVec3 up = Vec3Cross(normal, side);
	up = Vec3Normalize(up);
	EVec3 dir = Vec3Normalize(direction);
	side *= size/2;
	up *= size/2;
	dir *= size/2;

	//	Points of bounding cube
	EVec3 p0 = v.position + dir + up + side;
	EVec3 p1 = v.position + dir + up - side;
	EVec3 p2 = v.position + dir - up + side;
	EVec3 p3 = v.position + dir - up - side;
	EVec3 p4 = v.position - dir + up + side;
	EVec3 p5 = v.position - dir + up - side;
	EVec3 p6 = v.position - dir - up + side;
	EVec3 p7 = v.position - dir - up - side;

	IPxTriMesh temp = Geometry()->CreateTriMesh(result->GetFormat());

	//	Cut mesh
	temp = TrimMesh(p0, p1, p5, this);
	temp = TrimMesh(p6, p2, p0, temp);
	temp = TrimMesh(p6, p7, p3, temp);
	temp = TrimMesh(p1, p3, p7, temp);
	temp = TrimMesh(p2, p3, p1, temp);
	temp = TrimMesh(p4, p5, p7, temp);
	
	temp->MergeVertices();
	result->Merge(temp);

	if (result->IsEmpty())
		return false;

	EPlane plane1 = PlaneFromPoints(p0, p1, p5);
	EVec3 normal1(plane1.a, plane1.b, plane1.c);
	normal1 = Vec3Normalize(normal1);

	EPlane plane2 = PlaneFromPoints(p6, p2, p0);
	EVec3 normal2(plane2.a, plane2.b, plane2.c);
	normal2 = Vec3Normalize(normal2);

	ETriMesh* mptr = result.to<ETriMesh>();
	mptr->shading_groups.clear();

	//	Compute texcoord depending on a distances from planes
	for (uint i = 0; i < mptr->vertices.size(); i++){
		float u = abs((Vec3Dot(mptr->vertices[i].position, normal1) + plane1.d) / size);
		float v = abs((Vec3Dot(mptr->vertices[i].position, normal2) + plane2.d) / size);
		mptr->vertices[i].uv0 = ETexCoord(u, v);
	}

#endif
	return true;
}